package tasks.zhuanyeji.分布式任务调度;

/**
 * 某分布式任务调度系统有taskNum个任务（编号从 1 到 taskNum）需要调度，调度策略：
 * <p>
 * 任务之间可能存在依赖关系，且无循环依赖，如任务1 依赖任务2，那么要等待任务2执行完才能执行任务1； 如果任务之间没有依赖关系，则可以并发执行（假设并发所需资源是充足的）。 现给出任务间的依赖关系relations，并假设每个任务的执行时间恒为 1 分钟，请计算执行完这 taskNum 个任务所需的最短时间（单位分钟）。
 * <p>
 * 输入 1 <= taskNum <= 1000 0 <= relations.length <= 500000，relations[i] = [id1, id2]，表示任务1 依赖任务2， 1 <= id1, id2 <= taskNum
 * <p>
 * 输出 一个整数，代表执行完所有任务的最短时间。复制输入： 3 [[1, 2]] 复制输出： 2 解释： 总共三个任务，任务1依赖任务2，任务2、任务3可以并发执行，最后执行任务1，最短时间为2分钟。
 * <p>
 * 样例2 复制输入： 9 [[1, 2], [2, 3], [2, 4], [4, 5], [6, 4], [8,7]] 复制输出： 4 ； 用java帮我实现它；class Solution { // 注：relations[i] = [id1, id2] int getMinTime(int taskNum, int[][] relations) { return -1; } }
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {

    public static void main(String[] args) {
        int [][]arr = {{1, 2},{2, 3}, {2, 4}, {4, 5}, {6, 4}, {8,7}};
        int minTime = new Solution().getMinTime(9, arr);
        System.out.println(minTime);
    }

    public int getMinTime(int taskNum, int[][] relations) {
        // 构建图：graph[i] 表示节点 i 指向的节点列表（后继节点）
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= taskNum; i++) {
            graph.add(new ArrayList<>());
        }
        int[] indegree = new int[taskNum + 1]; // 入度数组

        // 处理依赖关系：每个关系[id1, id2]表示id1依赖id2 -> 边为 id2 -> id1
        for (int[] relation : relations) {
            int id1 = relation[0];
            int id2 = relation[1];
            graph.get(id2).add(id1); // id2指向id1
            indegree[id1]++; // id1的入度增加
        }

        Queue<Integer> queue = new LinkedList<>();
        // 将所有入度为0的节点加入队列
        for (int i = 1; i <= taskNum; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        /**
         * bfs 广度搜索
         */
        int minutes = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 当前层的所有节点
            for (int i = 0; i < size; i++) {
                int node = queue.poll();
                // 遍历当前节点的所有后继节点
                for (int next : graph.get(node)) {
                    indegree[next]--;
                    if (indegree[next] == 0) {
                        queue.offer(next);
                    }
                }
            }
            minutes++; // 完成当前层，时间+1
        }

        return minutes;
    }
}

